//
// Created by 高森森 on 2022/10/11.
//

#ifndef LEETCODE_SOLUTION_21_H
#define LEETCODE_SOLUTION_21_H

#include<bits/stdc++.h>
using namespace std;
const int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
class solution_21 {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>matrix(n,vector<int>(n,0));
        int cnt=0;
        int status=0;
        dfs(matrix,n,cnt,0,0,status);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    void dfs(vector<vector<int>>&matrix,int n,int cnt,int i,int j,int status){
        cnt++;
        matrix[i][j]=cnt;
        if(cnt==n*n){
            return;
        }
        int nextI=i+direction[status][0];
        int nextJ=j+direction[status][1];
        if(nextI<0||nextI>=matrix.size()||nextJ<0||nextJ>=matrix[0].size()||matrix[nextI][nextJ]!=0){
            status=(status+1)%4;
        }
        dfs(matrix,n,cnt,i+direction[status][0],j+direction[status][1],status);
    }
};


#endif //LEETCODE_SOLUTION_21_H
